package main

import (
	"fmt"
)

/*
*
这道题利用了些技巧
![](http://cdn.bsummer.cn/20200415040125.png)

https://www.youtube.com/watch?v=Ah__jYQXp0k
*/
func main() {
	/**
	  4 1
		  8 4 5
	5 6 1
	*/
	//mix := &ListNode{
	//	Val:  8,
	//	Forward: &ListNode{
	//		Val:  4,
	//		Forward: &ListNode{
	//			Val:  5,
	//			Forward: nil,
	//		},
	//	},
	//}
	//
	//l1:=&ListNode{
	//	Val:  4,
	//	Forward: &ListNode{
	//		Val:  1,
	//		Forward: mix,
	//	},
	//}
	//
	//l2:=&ListNode{
	//	Val:  5,
	//	Forward: &ListNode{
	//		Val:  6,
	//		Forward: &ListNode{
	//			Val:  1,
	//			Forward: mix,
	//		},
	//	},
	//}

	//n1 := &ListNode{
	//	Val:  1,
	//	Forward: nil,
	//}
	//n2 := &ListNode{
	//	Val:  2,
	//	Forward: nil,
	//}
	//n3 := &ListNode{
	//	Val:  3,
	//	Forward: nil,
	//}
	//
	//n4 := &ListNode{
	//	Val:  4,
	//	Forward: nil,
	//}
	//n5 := &ListNode{
	//	Val:  5,
	//	Forward: nil,
	//}
	//
	//n1.Forward = n2
	//n2.Forward = n3
	//n3.Forward = n4
	//n5.Forward = n3
	//
	//fmt.Println(getIntersectionNode(n1, n5))

	/**
	2 6 4
	  1 5
	*/
	l1 := &ListNode{
		Val: 2,
		Next: &ListNode{
			Val: 6,
			Next: &ListNode{
				Val:  4,
				Next: nil,
			},
		},
	}
	l2 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val:  5,
			Next: nil,
		},
	}
	fmt.Println(getIntersectionNode(l1, l2))
}

/*
*
对于本题，我们要考虑数量链表数量相等和链表数量不等的情况
两链表节点数相等

	有交点: 无需切换头结点就可以判断出
	无交点: 无需切换头结点，遍历到末尾nil就可以判断出

两链表节点数不等

	有交点: 切换头结点可判断出
	无交点: 切换头结点遍历到结束可判断出

corner case:
对于headA 与head B不相交的情况,最终i j都被赋值nil，跳出循环
举例1
headA:	2 6 4
headB:	  1 5

2 1
6 5
4 nil
nil 2
1 6
5 4
nil nil 此时退出

在实现上要注意让i j可以赋值nil，不要直接跳过nil
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	i, j := headA, headB
	// 注意点1: 对于不相交的两个链表，最终也会因为都是nil而结束 这个条件相当巧妙
	for i != j {
		// 这里不能是a.Next==nil,使用a.Next==nil的话a将永远无法达到nil，陷入无限循环
		if i == nil { // 注意点2: 这里不能是i.Forward==nil 需要让i,j有等于nil的时候，否则会遇到i,j永远不为nil，循环无法正常退出
			i = headB
		} else {
			i = i.Next
		}

		if j == nil {
			j = headA
		} else {
			j = j.Next
		}
		fmt.Println(i, j)
	}

	// 返回的i就是相遇的节点
	return i
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	p, q := headA, headB
	for p != q {
		if p == nil {
			p = headB
		} else {
			p = p.Next
		}

		if q == nil {
			q = headA
		} else {
			q = q.Next
		}
	}
	return p
}
